package fun.ticsmyc.sort;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

import java.util.Arrays;

/**
 * 堆排序
 * @author Ticsmyc
 * @package fun.ticsmyc.sort
 * @date 2020-02-11 14:51
 */
public class HeapSort {

    public void heapSort(int[] arr){
        if(arr==null || arr.length <2){
            return ;
        }
        for(int i=0 ; i<arr.length ;++i){
            heapInsert(arr,i);
        }
        int size = arr.length;
        //与最后一位交换
        while(size > 1 ){
            ArrayTools.swap(arr,0,--size);
            heapify(arr,0,size);
        }
    }

    /**
     * 1. 从下向上调整。
     * @param arr
     * @param index
     */
    public void heapInsert(int[] arr, int index){
        while(arr[index] > arr[(index-1)/2]){
            ArrayTools.swap(arr,index,(index-1)/2);
            index=(index-1)/2;
        }
    }

    /**
     * 2.从上向下调整
     * @param arr
     * @param index
     * @param size
     */
    public void heapify(int[] arr,int index, int size){
        int left = index*2+1;
        while(left < size){
            //有叶子
            int bigest = (left+1 < size && arr[left+1]>arr[left]) ? left+1 : left;
            if(arr[index] < arr[bigest]){
                ArrayTools.swap(arr,index,bigest);
                index=bigest;
                left = index*2+1;
            }else{
                break;
            }
        }
    }


    @Test
    public void test(){

        //测试次数
        int testTime=5_000_000;
        //数组大小
        int size=10;
        //数组值 -100 ~ +100
        int value=100;
        boolean succeed =true;

        for(int i=0;i<testTime;++i){
            int[] arr1 = ArrayTools.generateRandomArray(size,value);

            int[] arr2 = Arrays.copyOf(arr1,arr1.length);
            int[] arr3 = Arrays.copyOf(arr1,arr1.length);

            heapSort(arr1);
            ArrayTools.rightSortMethod(arr2);
            if(!Arrays.equals(arr1,arr2)){
                succeed=false;
                //打印原数组
                ArrayTools.printArray(arr3);
                break;
            }
        }
        System.out.println( succeed ? "nice" : "Fucking fucked!");
    }

    @Test
    public void testOne(){
        int[] arr1 =new int[]{62,  -14,  21 , 42  };
        ArrayTools.printArray(arr1);
        heapSort(arr1);
        ArrayTools.printArray(arr1);
    }

}
